package algorithmlearn.sort;

import java.util.LinkedList;

//graph traversal  图遍历 path search algorithm
//1.dijkstra 实现最短路径搜索
public class PathSearchAlgorithm {

    private class Graph {
        int v;
        LinkedList<Edge>[] adj;

        public Graph(int v) {
            this.v = v;
            adj = new LinkedList[v];
            for (int i = 0; i < v; i++) {
                adj[i] = new LinkedList<>();
            }
        }

        public void addEdg(int s, int t, int w) {
            adj[s].add(new Edge(s, t, w));
        }

        private class Edge {
            public int sid; // 边的起始顶点编号
            public int tid; // 边的终止顶点编号
            public int w; // 权重

            public Edge(int sid, int tid, int w) {
                this.sid = sid;
                this.tid = tid;
                this.w = w;
            }
        }

        //实现dijkstra
        public void dijkstra(int s, int t) { // 从顶点 s 到顶点 t 的最短路径
            int[] predecessor = new int[this.v]; // 用来还原最短路径
            Vertex[] vertexes = new Vertex[this.v];
            for (int i = 0; i < this.v; ++i) {
                vertexes[i] = new Vertex(i, Integer.MAX_VALUE);
            }
            PriorityQueue queue = new PriorityQueue(this.v);// 小顶堆
            boolean[] inqueue = new boolean[this.v]; // 标记是否进入过队列
            vertexes[s].dist = 0;
            queue.add(vertexes[s]);
            inqueue[s] = true;
            while (!queue.isEmpty()) {
                Vertex minVertex = queue.poll(); // 取堆顶元素并删除
                if (minVertex.id == t) break; // 最短路径产生了
                for (int i = 0; i < adj[minVertex.id].size(); ++i) {
                    Edge e = adj[minVertex.id].get(i); // 取出一条 minVetex 相连的边
                    Vertex nextVertex = vertexes[e.tid]; // minVertex-->nextVertex
                    if (minVertex.dist + e.w < nextVertex.dist) { // 更新 next 的 dist
                        nextVertex.dist = minVertex.dist + e.w;
                        predecessor[nextVertex.id] = minVertex.id;
                        if (inqueue[nextVertex.id] == true) {
                            queue.update(nextVertex); // 更新队列中的 dist 值
                        } else {
                            queue.add(nextVertex);
                            inqueue[nextVertex.id] = true;
                        }
                    }
                }
            }
            // 输出最短路径
            System.out.print(s);
            print(s, t, predecessor);
        }

        private void print(int s, int t, int[] predecessor) {
            if (s == t) return;
            print(s, predecessor[t], predecessor);
            System.out.print("->" + t);
        }
    }

    // 下面这个类是为了 dijkstra 实现用的
    private class Vertex {
        public int id; // 顶点编号 ID
        public int dist; // 从起始顶点到这个顶点的距离

        public Vertex(int id, int dist) {
            this.id = id;
            this.dist = dist;
        }
    }

    //实现优先级队列，利用堆，小顶堆
    private class PriorityQueue {
        private Vertex[] nodes;
        private int size;

        public PriorityQueue(int v) {
            this.nodes = new Vertex[v + 1];
            this.size = v;
        }

        public Vertex poll() {
            if (size == 0)
                return null;
            int s = --size;
            Vertex result = nodes[0];
            Vertex x = nodes[s];
            nodes[s] = null;
            if (s != 0)
                siftDown(0, x);
            return result;
        }

        public boolean add(Vertex x) {
            if (x == null)
                throw new NullPointerException();
            int i = size;

            if (i == 0)
                nodes[0] = x;
            else
                siftUp(i, x);
            return true;
        }

        // 更新结点的值，并且从下往上堆化，重新符合堆的定义。时间复杂度 O(logn)。
        public boolean update(Vertex x) {
            int i = indexOf(x);
            if (i == -1)
                return false;
            else {
                updateAt(i,x);
                return true;
            }
        }

        private int indexOf(Vertex x) {
            if (x != null) {
                for (int i = 0; i < size; i++)
                    if (x.id == nodes[i].id)
                        return i;
            }
            return -1;
        }

        public boolean isEmpty() {
            return size==0;
        }

        private Vertex updateAt(int i,Vertex x) {
            int s = --size;
            if (s == i) // updated last element
                siftUp(i, x);
            else {
                siftDown(i, x);
                if (nodes[i] == x) {
                    siftUp(i, x);
                    if (nodes[i] != x)
                        return x;
                }
            }
            return null;
        }

        /**
         * Inserts item x at position k, maintaining heap invariant by
         * promoting x up the tree until it is greater than or equal to
         * its parent, or is the root.
         *
         * To simplify and speed up coercions and comparisons. the
         * Comparable and Comparator versions are separated into different
         * methods that are otherwise identical. (Similarly for siftDown.)
         *
         * @param k the position to fill
         * @param x the item to insert
         */
        private void siftUp(int k, Vertex x) {
            while (k > 0) {
                int parent = (k - 1) >>> 1;
                Vertex e = nodes[parent];
                if (x.dist - e.dist >= 0)
                    break;
                nodes[k] = e;
                k = parent;
            }
            nodes[k] = x;
        }

        /**
         * Inserts item x at position k, maintaining heap invariant by
         * demoting x down the tree repeatedly until it is less than or
         * equal to its children or is a leaf.
         *
         * @param k the position to fill
         * @param x the item to insert
         */
        private void siftDown(int k, Vertex x) {
            int half = size >>> 1;        // loop while a non-leaf
            while (k < half) {
                int child = (k << 1) + 1; // assume left child is least
                Vertex c = nodes[child];
                int right = child + 1;
                if (right < size &&
                        c.dist - nodes[right].dist > 0)
                    c = nodes[child = right];
                if (x.dist - c.dist <= 0)
                    break;
                nodes[k] = c;
                k = child;
            }
            nodes[k] = x;
        }
    }
}
